iT邦幫忙

2021 iThome 鐵人賽

DAY 8
0
自我挑戰組

Leetcode刷題筆記系列 第 8

[Day 8] Leetcode 1189. Maximum Number of Balloons (C++)

  • 分享至 

  • xImage
  •  

前言

飆車回家又是11點多了,發現今天的daily challenge是easy就順手解個吧!題目在這邊:1189. Maximum Number of Balloons

想法

這就真的蠻簡單沒什麼好說的XD 但我們可以做的就是用盡量少的時間跟空間~
看到這題目應該很明顯就是我們需要去統計各個字母出現的次數,然後去求5個字母的最小次數(lo要除以2)
有幾種直覺做法:

  • 次數表: 我們可以跟昨天一樣,建立一個大小為62的vector,用text[i]-'a'去存每個字母的出現次數
    針對這點,因為我們只care balloon這 'b','a','l','o','n'這五個字母,所以我們可以空間優化為只存5個字母就好,至於怎麼存,只有5個可以直接寫死,也是可以用unordered map來存比較好看一點(cnt[i]++),不過這空間有沒有省到就難說了。

btw每次遇到這種計算頻率就會很想念python的counter可以秒殺~ 如果用python的話強力推薦有很多人實作好的function可以直接用,而且時間都還比自己慢慢算快很多;不過python跟C++的執行速度也不在同一個等級就是了XD

  • 次數計算:我們可以用STL的count (count(s.begin(), s.end(), 'a');) 來直接計算字母出現的頻率,但就時間而言,每次的count等於都要去掃一遍整個string,5個字母都要掃就需要掃五次,所以還是手動掃過一輪直接一起計算就好。
    完整code如下:
class Solution {
public:
    int maxNumberOfBalloons(string text) {
        // record frequency only for 'b','a','n','l','o'
        vector<int> cnt(5);
        char tmp;
        for(int i=0;i<text.length();++i){
            tmp = text[i];
            if(tmp=='b'){
                cnt[0]++;
            }
            else if(tmp=='a'){
                cnt[1]++;
            }else if(tmp=='n'){
                cnt[2]++;
            }else if(tmp=='l'){
                cnt[3]++;
            }else if(tmp=='o'){
                cnt[4]++;
            }
        }
        return min({cnt[0], cnt[1], cnt[2], cnt[3]/2, cnt[4]/2});
    }
};

也可以像我上面提到的unordered_map寫法

class Solution {
public:
    int maxNumberOfBalloons(string text) {
        // record frequency only for 'b','a','n','l','o'
        unordered_map<char, int> cnt;
        char tmp;
        for(int i=0;i<text.length();++i){
            tmp = text[i];
            if(tmp=='b' || tmp=='a' || tmp=='l' || tmp=='o' || tmp=='n'){
                cnt[tmp]++;
            }
        }
        return min({cnt['b'], cnt['l'], cnt['o']/2, cnt['l']/2, cnt['n']});
        
    }
};

第二個這個寫法,在最後取cnt['b']...的時候可能會比較快~ 不過這有待更多查證實驗了

結語

整個code不是很美觀,但是就求一個(自己覺得?)快XD 至少除了寫完可以accept都可以多思考一下有哪邊是可以優化的地方~
當然如果要寫的general就不用寫死這麼多條件,直接把26個字母用昨天計算次數表的方式來存就好,code可以整個簡潔很多
希望明天的題目可以是easy~medium但是有梗的XD 不然內容好空虛啊
然後可以早點下班回來慢慢寫(結語怎麼變成在許願)~


上一篇
[Day 7] Leetcode 621. Task Scheduler (C++)
下一篇
[Day 9] Leetcode 917. Reverse Only Letters (C++)
系列文
Leetcode刷題筆記30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言